//小偷要偷窃一系列房子，每个房子有价值values[i],但小偷不能偷取连续的两间房子，求最后小偷偷到的最大价值
//dp意义：到第i间房子时能偷到的最大价值
//dp递推：偷i或不偷i，前者就是dp[i-1],后者就是dp[i-2]+values[i]，取最大值即可
#include <vector>
#include <algorithm>
using std::vector;
using std::max;
int rob(vector<int>& nums) {
    int N=nums.size();
    vector<int> dp(N+1,0);
    //初始前两个，dp[0]=0;
    dp[1]=nums[0];
    for(int i=2;i<=N;i++){
        //偷i就不能偷i-1罢了
        dp[i]=max(dp[i-1],dp[i-2]+nums[i-1]);
    }
    
    return dp[N];

}


//打家劫舍问题升级版，隐藏的打家劫舍问题
//删除并获得点数
//给出一个整数数组，每次操作可以选一个数nums[i]，但要删除其余所有值为nums[i]+1和nums[i]-1的数，求取完点数最大值
/*咋一看跟dp没什么关系，但排列一下数组就会发现其实是打家劫舍，取了nums[i],隔壁的两个数就不能取
注意这时价值不是nums[i]，而是要乘上nums[i]的个数，因为可以重复取
而且排序后两个数是否相邻的判断是差绝对值是否等于1，
如果大于1，就是不相邻，那么如果在中间插一个0，就可以让他们可以同时取了

*/

//所以将nums可以变成两个数组：homes和value,房间和价值，遍历nums时，home和value要同步，因为这俩用的时候是对应的
int deleteAndEarn(vector<int>& nums){
    if(!nums.size()) return 0;
    //先排序才能比较
    sort(nums.begin(),nums.end());
    vector<int> homes;
    vector<int> values;
    homes.push_back(0);
    values.push_back(0);
    homes.push_back(nums[0]);
    values.push_back(homes[1]);
    int phome=1;//homes和add的索引要用他
    //处理nums数组，转化为打家劫舍模型
    for(int i=1;i<nums.size();i++){
        if(nums[i]!=nums[i-1]){
            if(nums[i]-nums[i-1]>1){
                //如果差大于1不用删除，就不是相邻房子要插入一个0
                homes.push_back(0);
                values.push_back(0);
                phome++;
                homes.push_back(nums[i]);
                values.push_back(nums[i]);
                phome++;
            }
            else{
                homes.push_back(nums[i]);
                values.push_back(nums[i]);
                phome++;
            }
        }
        else values[phome]+=nums[i];
    }
    vector<int> dp(values.size(),0);//dp[0]=0
    dp[1]=values[1];
    for(int i=2;i<dp.size();i++)
        dp[i]=max(dp[i-1],dp[i-2]+values[i]);
    return dp[dp.size()-1];

}
//实际上可以看到，home数组是没有用的，因为values也在放入0，那么只用values就可以满足打家劫舍模型了
int deleteAndEarn_(vector<int>& nums){
    if(!nums.size()) return 0;
    //先排序才能比较
    sort(nums.begin(),nums.end());
    vector<int> values;
    values.push_back(0);   
    values.push_back(nums[0]);
    int phome=1;//homes和add的索引要用他
    //处理nums数组，转化为打家劫舍模型
    for(int i=1;i<nums.size();i++){
        if(nums[i]!=nums[i-1]){
            if(nums[i]-nums[i-1]>1){
                //如果差大于1不用删除，就不是相邻房子要插入一个0
                values.push_back(0);
                phome++;
                values.push_back(nums[i]);
                phome++;
            }
            else{
                values.push_back(nums[i]);
                phome++;
            }
        }
        else values[phome]+=nums[i];
    }
    
    //dp环节
    vector<int> dp(values.size(),0);//dp[0]=0
    dp[1]=values[1];
    for(int i=2;i<dp.size();i++)
        dp[i]=max(dp[i-1],dp[i-2]+values[i]);
    return dp[dp.size()-1];

}
